#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

/**
 * 给定 n 个物品，每个物品的重量为 weights[i]、价值为 values[i]，以及一个最大承重 capacity 的背包。

目标：从这些物品中选择一些放入背包，使得总重量不超过 capacity，且总价值最大。
注意：每个物品只能选 一次（不能重复选），因此称为 0-1 背包。

1. 状态定义
使用一个二维数组 dp[i][w] 表示：

在前 i 个物品中选择，且当前背包容量为 w 的情况下，能获得的最大价值。
2. 状态转移方程
对于第 i 个物品（索引从 1 开始）：

if weights[i - 1] <= w:
    dp[i][w] = max(
        dp[i - 1][w],                             // 不选第 i 个物品
        dp[i - 1][w - weights[i - 1]] + values[i - 1]  // 选第 i 个物品
    )
else:
    dp[i][w] = dp[i - 1][w]  // 无法选该物品
3. 初始条件
dp[0][w] = 0 对于所有 w：没有物品时，价值为 0
dp[i][0] = 0 对于所有 i：背包容量为 0 时，无法装入任何物品
 * 
 */
int knapsack_01(const vector<int>& weights, const vector<int>& values, int capacity) {
    int n = weights.size();
    vector<vector<int>> dp(n + 1, vector<int>(capacity + 1, 0));

    for (int i = 1; i <= n; ++i) {
        for (int w = 0; w <= capacity; ++w) {
            if (weights[i - 1] <= w) {
                dp[i][w] = max(
                    dp[i - 1][w],
                    dp[i - 1][w - weights[i - 1]] + values[i - 1]
                );
            } else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }

    return dp[n][capacity];
}

int knapsack_01_optimized(const vector<int>& weights, const vector<int>& values, int capacity) {
    int n = weights.size();
    vector<int> dp(capacity + 1, 0);

    for (int i = 0; i < n; ++i) {
        for (int w = capacity; w >= weights[i]; --w) {
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i]);
        }
    }

    return dp[capacity];
}

int main() {
    vector<int> weights = {2, 3, 4, 5};  // 物品重量
    vector<int> values = {3, 4, 5, 6};   // 物品价值
    int capacity = 5;                    // 背包最大承重

    cout << "最大价值: " << knapsack_01(weights, values, capacity) << endl;
    return 0;
}